package com.apkcore.bl;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * https://leetcode-cn.com/problems/minimum-window-substring/
 */
public class _76最小覆盖子串 {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(new _76最小覆盖子串().minWindow(s, t));
    }

    public String minWindow(String s, String t) {
        Map<Character, Integer> needs = new HashMap<>();
        Map<Character, Integer> windows = new HashMap<>();

        int left = 0;
        int right = 0;

        int valid = 0;
        int start = 0;
        int len = Integer.MAX_VALUE;

        char[] tC = t.toCharArray();
        char[] sC = s.toCharArray();
        for (char c : tC) {
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }

        while (right < s.length()) {
            char c = sC[right];
            right++;
            if (needs.containsKey(c)) {
                windows.put(c, windows.getOrDefault(c, 0) + 1);
                if (windows.getOrDefault(c, 0).equals(needs.get(c))) {
                    valid++;
                }
            }


            while (valid == needs.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = sC[left];
                left++;
                if (needs.containsKey(d)) {
                    if (windows.getOrDefault(d, 0).equals(needs.get(d))) {
                        valid--;
                    }
                    windows.put(d, windows.getOrDefault(d, 1) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

//    public String minWindow2(String s, String t) {
//        Map<Character, Integer> needs = new HashMap<>();
//        Map<Character, Integer> windows = new HashMap<>();
//        int left = 0;
//        int right = 0;
//        int start = 0;
//        int len = Integer.MAX_VALUE;
//
//
//        int valid = 0;
//        char[] sc = s.toCharArray();
//        char[] tc = t.toCharArray();
//        for (char c : tc) {
//            needs.put(c, needs.getOrDefault(c, 0) + 1);
//        }
//
//        while (right < s.length()) {
//            char c = sc[right];
//            right++;
//
//            if(needs.containsKey(c)){
//                windows.put(c,windows.getOrDefault(c,0)+1);
//                if(Objects.equals(needs.get(c), windows.getOrDefault(c, 0))){
//                    valid++;
//                }
//            }
//            while (valid == needs.size()) {
//                if (right - left < len) {
//                    start = left;
//                    len = right - left;
//                }
//
//                char d = sc[left];
//                left++;
//                if(needs.containsKey(d)){
//                    if(Objects.equals(needs.get(d), windows.getOrDefault(d, 0))){
//                        valid--;
//                    }
//                    windows.put(d,windows.getOrDefault(d,1)-1);
//                }
//
//            }
//        }
//        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
//    }

//    public String minWindow2(String s, String t) {
//        Map<Character, Integer> needs = new HashMap<>();
//        Map<Character, Integer> windows = new HashMap<>();
//
//        char[] sc = s.toCharArray();
//        char[] tc = t.toCharArray();
//
//        for (char c : tc) {
//            needs.put(c, needs.getOrDefault(c, 0) + 1);
//        }
//
//        int left = 0;
//        int right = 0;
//        int start = 0;
//        int len = Integer.MAX_VALUE;
//        int valid = 0;
//
//        while (right < sc.length) {
//            char c = sc[right];
//            right++;
//            //
//
//            while () {
//                while (right - left < len) {
//                    start = left;
//                    len = right - left;
//                }
//
//                char d = sc[left];
//                left++;
//
//                ///
//            }
//        }
//
//    }
}